\extitle{2}{同余与同余类}

\section{整 数同 余}
\begin{exercise}
详细证明定理 1 中各项。
\end{exercise}

\begin{solution}
略。
\end{solution}

\begin{exercise}
讨论： (1) $n^{2} \equiv ? \left(\mod 4\right)$. (2) $n^{2} \equiv ? \left(\mod 8\right)$.
\end{exercise}

\begin{solution}
记 \(n = {2k} + r\left( {r = 0, 1}\right)\), 则 \({n}^{2} \equiv  4{k}^{2} + {4kr} + {r}^{2} \equiv  {r}^{2} = 0\) 或 \(1\left( {\;\mod 4}\right)\), 
当 \(n\) 为偶数或奇数。
记 \(n = {4k} + r\left( {r = 0, 1, 2, 3}\right), {n}^{2} \equiv  {16}{k}^{2} + {8kr} + {r}^{2} \equiv  {r}^{2} = 0, 1, 4\)  \(\left( {\;\mod 8}\right)\), 当 \(r = 0,  \pm  1, 2\).
\end{solution}

\begin{exercise}
考虑如何判断 $11$ 整除 $n$.
\end{exercise}

\begin{solution}
因 \({10} \equiv   - 1\left( {\;\mod {11}}\right), {10}^{2} \equiv  1\left({\mod {11}}\right)\), 故
\[
n =  {a}_{0} + {a}_{1}{10} + \cdots   +{a}_{s}{10}^{s}   \equiv  {a}_{0} - {a}_{1} + {a}_{2} - \cdots  + {\left( -1\right) }^{s - 1}{a}_{s}\;\left( {\;\mod {11}}\right) .
\]
故可以说“ \({11} \mid  n\) ” 当且仅当 “$11$ 整除 \(n\) 的十进位表示的数字正负交错和”.
\end{solution}

\begin{exercise}
考虑如何判断 $13$ 整除 $n$,  以及 $7$ 整除 $n$.
\end{exercise}

\begin{solution}
由 \(7 \cdot  {11} \cdot  {13} = {1001}\), 可知 \({1000} \equiv   - 1\left( \mod {13}\right)\). 故
\[
n = {b}_{r}{1000}^{r} + \cdots  + {b}_{1}{1000} + {b}_{0} \equiv  {b}_{0} - {b}_{1} + {b}_{2} - \cdots  + {\left( -1\right) }^{r - 1}{b}_{r} \left( \mod {13} \right) .
\]
故可以说“ \({13} \mid  n\) ” 当且仅当 “ $13$ 整除 \(n\) 的千进位表示的数字正负交错和”.

同理可得 \(7 \mid  n\) 的判断方法。
\end{solution}

\begin{exercise}
设今天是星期一， 问 $2020^{2020}$ 天之后是星期几? $10^{10^{2020}}$ 天之后呢?
\end{exercise}

\begin{solution}
 (1) \({2}^{3} = 8 \equiv  1\left( {\mod 7}\right)\), 故 \({2}^{3k} \equiv  1\left( {\mod 7}\right)\), 故知
\[
{2020}^{{2020}} = {\left( 7 \cdot  {288} + 4\right) }^{{2020}} \equiv  {2}^{{4040}} \equiv  {2}^{2} \equiv  4 \left(\mod 7\right) 
\]
(可以用弃 3 法得到$4040\equiv 2\left( \mod 3 \right)$);
或由 \({3}^{3} = {27} \equiv   - 1\left( {\mod 7}\right)\), 知
\[
{2020}^{2020} \equiv  {\left( -3\right) }^{2020} = {3}^{3 \cdot  {673} + 1} \equiv  {\left( -1\right) }^{673} \cdot  3 \equiv   - 3 \equiv  4 \left( {\mod 7}\right) .
\]

(2) 因 \({10}^{3} \equiv  {3}^{3} \equiv   - 1, {10}^{6} \equiv  {3}^{6} \equiv  1\left( {\mod 7}\right)\), 故对指数 \({10}^{2020}\) 要求模 6 同余。 因
\[
{10} \equiv  4 \left( {\mod 6}\right), {10}^{2} \equiv  4, 
\]
故 \({10}^{m} \equiv  4\left( {\mod 6}\right)\) (对任意正整数 \(m\)). 故
\[
{10}^{{10}^{2020}} \equiv  {10}^{{6k} + 4} \equiv  1 \cdot  {3}^{4} \equiv  4 \left( {\mod 7}\right) .
\]
故知 \({2020}^{{2020}}\) 或 \({10}^{{10}^{2020}}\) 天之后都是星期五。
\end{solution}

\begin{exercise}
对于整数 $n$ 的 “八进位表示”(计算机和信息学中常用),  讨论小素数 $p$ 整除 $n$ 的判别方法。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
证明： 若 $m-p \mid m n+p q$,  则 $m-p \mid m q+n p$.
\end{exercise}

\begin{solution}
\(m \equiv  p\left( {{\mod m} - p}\right)\), 故 \(0 \equiv  {mn} + {pq} \equiv  {np} + {mq}\left( {{\mod m} - p}\right)\).
\end{solution}

\begin{exercise}
写出所有的由 $3$ 个(正)素数组成的公差为 $8$ 的等差数列。
\end{exercise}

\begin{solution}
设数列为 \(p, p + 8, p + {16}\), 模 $3$ 同余于 \(p, p + 2, p + 1\). 它们互不同余。 必有一个模 $3$ 为 $0$,
即是 $3$ (因是素数). 故数列只能是$3$, $11$, $19$. 
(若考虑负素数， 可由 \(\pm  3\) 开始，
加、减 $8$ 多次得到。)
\end{solution}

\begin{exercise}
最多能取多少正整数， 使其中任意 $3$ 个加起来是素数?
\end{exercise}

\begin{solution}
模 $3$ 的三类中只能从两类取 (否则， 三类的相加必为 $3$ 倍),  每类中最多取两个。 故最多 $4$ 个正整数。 例如：$1$, $3$, $7$, $9$; 或$1$, $7$, $5$, $11$.
\end{solution}

\begin{exercise}
$2011$ 年元旦是星期六， 问 $100$ 年后的元旦呢?
\end{exercise}

\begin{solution}
平年 $365$ 天模 $7$ 为 $1$ 天， 故每过一平年星期数加 $1$ . 再看此 $100$ 年有多少闰年： 有 $24$ 个 ($2010$ 年到 $2111$ 年共 $101$ 年， 是 $4$ 的 $25$ 倍多， 故共 $24$ 个闰年 (减去 $2100$ 年)). 故对星期数来说，过此 $100$ 年相当于过了 
\({100} + {24} \equiv  {54} \equiv  5\) (天) $(\mod 7)$,  
故 $100$ 年后元旦是星期四。
\end{solution}

\begin{exercise}
设 $f(x)=a_{n} x^{n}+\cdots+a_{1} x+a_{0}$ 为整系数多项式， $a_{0}$ 和 $a_{n}+\cdots+a_{1}+a_{0}$ 均为奇数， 证明： $f(x)$ 没有整数根。
\end{exercise}

\begin{solution}
  反证。假设有整数根 \({x}_{0}\). 若$x_0\equiv 0\left( \mod 2 \right)$,  则 
  \[
    0=f(x_0)\equiv f(0) =a_0\left( \mod 2 \right),  
  \]
  与$a_0$为奇数相矛盾。
  若$x_0\equiv 1\left( \mod 2 \right)$,  则 
  \[
    0=f(x_0)\equiv f(1) =a_n+\cdots+a_1+a_0\left( \mod 2 \right),  
  \]
  与$a_{n}+\cdots+a_{1}+a_0$为奇数相矛盾。
  这就证明了$f(x)$没有整数根。
  %实际上题设告诉我们$f(x)\left( \mod 2 \right)\in \ZZ/2\ZZ[x]$在$\ZZ/2\ZZ$ 中无根，
  %特别地，$f(x)$ 没有整数根。
\end{solution}

\begin{exercise}
证明： $f(x)=x^{5}+5 x^{3}+x^{2}-1$ 没有整数根。
\end{exercise}

\begin{solution}[解答一]
  $f(x)\left( \mod 4 \right)$没有整数根，故$f(x)$没有整数根。诚然，对任意的整数$n$, 
\[
  f(n)\left( \mod 4 \right)\in \left\{ f(0),  f(1),  f(2),  f(-1) \right\}\left( \mod 4 \right)=\left\{ 3, 2, 3, 2 \right\}\left( \mod 4 \right).
\]
这样$f(n)\neq 0$.
\end{solution}

\begin{solution}[解答二]
  由于$f$首一，$f$可能的整数根整除$f$的常数项$-1$,  故可能的整数根为$\pm1$.
  但$\pm1$非$f$的根。故$f$没有整数根。
\end{solution}

\begin{exercise}
证明：不存在非常数整系数多项式 $f(x)$ 使得 $f(n)$ 总是素数 (对任意整数 $n$).
\end{exercise}

\begin{solution}
反证法。 假设 \(f\left( n\right)\) 对任意整数 \(n\) 均为素数。 设 \(f\left( a\right)  = p\) 为素数，对任意整数 \(b \equiv  a\left( {\mod p}\right)\), 有 \(f\left( b\right)  \equiv  f\left( a\right)  \equiv  0\left( {\mod p}\right)\), 即 \(p \mid  f\left( b\right)\), 故 \(p =  \pm  f\left( b\right)\) (因 \(f\left( b\right)\) 为素数). 从而 \(b\) 是 \(f\left( x\right)  \mp  p\) 的根。 这种 \(b\) 有无限多，故 \(f\left( x\right)  - p\) 或 \(f\left( x\right)  + p\) 有无限多个根。 矛盾。
\end{solution}



\section{同 余 类 集}
\begin{exercise}
举出等价关系和非等价关系的例子若干， 并说明可按前者而不可按后者将对象分类的原因， 说明按前者分类的结果。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
证明： 
\begin{enumerate}[(1)]
\item $a \equiv b\left(\mod m\right) \Leftrightarrow \bar{a}=\bar{b}$. 
\item%(2)
$a \neq b\left(\mod m\right) \Leftrightarrow \bar{a} \cap \bar{b}=\emptyset$.
\end{enumerate}
\end{exercise}

\begin{solution}
一般地，我们有等价关系时，按照定义等价的元素落在同一个等价类，而不同的等价类是无交的。
\end{solution}

\begin{exercise}
讨论如下两概念的区别和联系： 模 $m$ 同余类集 $\mathbb{Z} / m \mathbb{Z}$,  模 $m$ 剩余系 $R(m)$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
对 $\mathbb{Z} / m \mathbb{Z}$ 中加法和乘法的定义， 为什么要验证其合理性? 为什么是合理的?
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
详细证明 $\mathbb{Z} / m \mathbb{Z}$ 中加法和乘法的性质 A1-A5,  M1-M3 和分配律。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
  列出 $\mathbb{Z} / m \mathbb{Z}$ 的乘法运算表， 找出所有的可逆元及其逆， 找出所有零因子 (分别对 $m=1, 2, 3, 4, 5, 6$).
\end{exercise}

\begin{solution}
  令$\mathbb{Z} / m \mathbb{Z}$中零因子构成的集合为$D(\mathbb{Z} / m \mathbb{Z})$.
  我们有
  \[
    \begin{aligned}
      (\ZZ/m\ZZ)^*&= \left\{ \bar{a}\mid (a,m)=1, 1\leqslant a\leqslant m \right\}\\
      &= \left\{ \bar{a}\mid \text{$a$不被$m$的任一素因子整除}, 1\leqslant a\leqslant m \right\},\\
      D(\ZZ/m\ZZ)&= \left\{ \bar{a}\mid (a,m)>1, 1\leqslant a< m \right\}\\
      &= \left\{ \bar{a}\mid \text{$a$被$m$的某个素因子整除}, 1\leqslant a<m\right\}.
    \end{aligned}
  \]
  %比如可以用Eratothenes筛法
  我们找到所有单位后，剩下的非零元素就是所有的零因子。
  特别地，我们知道：若$m$为素数，$\ZZ/m\ZZ$为域，所有非零元都是单位，没有零因子；否则$\ZZ/m\ZZ$非域，有零因子。
  \begin{enumerate}
    \item $m=1$. 此时$\ZZ/1 \ZZ=\left\{ 0 \right\}$为零环。乘法单位元为$0$.
      $0$的逆元是$0$. 无零因子。
    \item $m=2$. 此时$\ZZ/2\ZZ=\left\{ \bar{0},  \bar{1} \right\}$.
      $(\ZZ/2 \ZZ)^*=\left\{ \bar{1} \right\}$; $\bar{1}^{-1}=\bar{1}$. 无零因子。
    \item  $m=3$. 此时$\ZZ/3 \ZZ=\left\{ \bar{0},  \bar{1},  \bar{2} \right\}$.
      $(\ZZ/3 \ZZ)^*=\left\{ \bar{1},  \bar{2} \right\}$;
      $\bar{1}^{-1}=\bar{1}$,  $\bar{2}^{-1}=\bar{2}$. 无零因子。
    \item $m=4$. 此时$\ZZ/4 \ZZ=\left\{ \bar{0},  \bar{1},  \bar{2},  \bar{3} \right\}$.
      $(\ZZ/4 \ZZ)^*=\left\{ \bar{1},  \bar{3} \right\}$;
      $\bar{1}^{-1}=\bar{1}$,  $\bar{3}^{-1}=\bar{3}$. 
      $D(\mathbb{Z} / 4\mathbb{Z})=\{ \bar{2} \}$.
    \item $m=5$. 此时$\ZZ/5 \ZZ=\left\{ \bar{0},  \bar{1},  \bar{2},  \bar{3},  \bar{4} \right\}$.
      $(\ZZ/5 \ZZ)^*=\left\{ \bar{1},  \bar{2},  \bar{3},  \bar{4} \right\}$;
      $\bar{1}^{-1}=\bar{1}$; $\bar{2},  \bar{3}$ 互逆；$\bar{4}^{-1}=\bar{4}$. 
无零因子。
    \item $m=6$. 此时$\ZZ/6\ZZ=\left\{ \bar{0},  \bar{1},  \bar{2},  \bar{3},  \bar{4},  \bar{5} \right\}$.
      $(\ZZ/6\ZZ)^*=\left\{ \bar{1},  \bar{5} \right\}$;
      $\bar{1}^{-1}=\bar{1}$; $\bar{5}^{-1}=\bar{5}$. 
      $D(\ZZ/6\ZZ)=\{ \bar{2},  \bar{3},  \bar{4} \}$.
      乘法表为
      \[
        \begin{array}{c|cccccc}
          & \bar{0}& \bar{1}& \bar{2}& \bar{3}& \bar{4}& \bar{5} \\
          \hline
\bar{0}& \bar{0} & \bar{0}& \bar{0}& \bar{0}& \bar{0}& \bar{0}\\
 \bar{1}& \bar{0}& \bar{1}& \bar{2}& \bar{3}& \bar{4}& \bar{5} \\
 \bar{2}&  \bar{0}& \bar{2}& \bar{4} &\bar{0} & \bar{2}&\bar{4} \\
 \bar{3}& \bar{0} & \bar{3}& \bar{0} & \bar{3}&\bar{0} &\bar{3} \\
 \bar{4}&  \bar{0}& \bar{4}&\bar{2} &\bar{0} &\bar{4} &\bar{2} \\
 \bar{5}&  \bar{0}& \bar{5}&\bar{4} &\bar{3} &\bar{2} &\bar{1} 
        \end{array}
      \]
  \end{enumerate}
\end{solution}

\begin{exercise}
对 $\mathbb{Z} / 9 \mathbb{Z},  \mathbb{Z} / 10 \mathbb{Z},  \mathbb{Z} / 12 \mathbb{Z}$,  找出所有的可逆元及其逆， 找出所有零因子。
\end{exercise}

\begin{solution}
令$\mathbb{Z} / m \mathbb{Z}$中零因子构成的集合为$D(\mathbb{Z} / m \mathbb{Z})$.
  我们有
  \[
    \begin{aligned}
      (\ZZ/m\ZZ)^*&= \left\{ \bar{a}\mid (a,m)=1, 1\leqslant a\leqslant m \right\}\\
      &= \left\{ \bar{a}\mid \text{$a$不被$m$的任一素因子整除}, 1\leqslant a\leqslant m \right\},\\
      D(\ZZ/m\ZZ)&= \left\{ \bar{a}\mid (a,m)>1, 1\leqslant a< m \right\}\\
      &= \left\{ \bar{a}\mid \text{$a$被$m$的某个素因子整除}, 1\leqslant a<m\right\}.
    \end{aligned}
  \]
  %比如可以用Eratothenes筛法
  找到所有单位后，剩下的非零元素就是所有的零因子。
  \begin{enumerate}
    \item $m=9$. 
      $(\ZZ/9 \ZZ)^*=\left\{ \bar{1},  \bar{2},  \bar{4},  \bar{5},  \bar{7},  \bar{8} \right\}$;
      $\bar{1}^{-1}=\bar{1}$; $\bar{2},  \bar{5}$互逆；$\bar{4},  \bar{7}$互逆； $\bar{8}^{-1}=\bar{8}$. 
      $D(\mathbb{Z} / 9\mathbb{Z})=\{ \bar{3},  \bar{6} \}$.
    \item $m=10$. 
      $(\ZZ/10 \ZZ)^*=\left\{ \bar{1},  \bar{3},  \bar{7},  \bar{9} \right\}$;
      $\bar{1}^{-1}=\bar{1}$; $\bar{3},  \bar{7}$ 互逆；$\bar{9}^{-1}=\bar{9}$. 
      $D(\mathbb{Z} / 10 \mathbb{Z})=\{ \bar{2},  \bar{4},  \bar{5},  \bar{6},  \bar{8}  \}$.
    \item $m=12$. 
      $(\ZZ/12\ZZ)^*=\left\{ \bar{1},  \bar{5},  \bar{7},  \overline{11}   \right\}$;
      这些元素的逆都是自身。
      $D(\ZZ/12\ZZ)=\{ \bar{2},  \bar{3},  \bar{4},  \bar{6},  \bar{8},  \bar{9},  \overline{10} \}$.
  \end{enumerate}
\end{solution}

\begin{exercise}
在 $\mathbb{Z} / 7 \mathbb{Z}$ 中， 求出 $\left\{2^{k}\right\}, \left\{3^{k}\right\}$ $(k \in \mathbb{Z})$.
\end{exercise}

\begin{solution}
  注意到使得$2^k\equiv 1\left( \mod 7 \right)$的最小正整数$k$为$k=3$. 
  这样
  \[
    \left\{ \bar{2}^k \mid k\in \ZZ\right\}=\left\{ \bar{2}^0,  \bar{2},  \bar{2}^2 \right\}=\left\{ 1,  \bar{2},  \bar{4} \right\}.
  \]
  注意到使得$3^k\equiv 1\left( \mod 7 \right)$的最小正整数$k$为$k=6$. 
  因此$\left\{ \bar{3}^k \right\}$中包含$6$个元素且非零，必定为
  \[
    \left\{ \bar{3}^k \mid k\in \ZZ\right\}=\left\{ \bar{1},  \bar{2},  \bar{3},  \bar{4},  \bar{5},  \bar{6} \right\}.
  \]
\end{solution}

\begin{exercise}
在 $\mathbb{Z} / 8 \mathbb{Z}$ 中， 求出 $\left\{2^{k}\right\}, \left\{6^{k}\right\}, \left\{3^{k}\right\}, \left\{5^{k}\right\}, \left\{7^{k}\right\}$ ($k$为正整数).
\end{exercise}

\begin{solution}
\begin{enumerate}
  \item  我们有$\bar{2}^3=0$. 进而易知$\left\{\bar{2}^{k}\mid k\in\NN\right\}=
    \left\{ \bar{2},  \bar{2}^2,  0 \right\}=\left\{  \bar{2},  \bar{4},  0 \right\}$.
  \item 我们有$\bar{6}^3=0$. 进而易知$\left\{\bar{6}^{k}\mid k\in\NN\right\}=
    \left\{ \bar{6},  \bar{6}^2,  0 \right\}=\left\{  \bar{6},  \bar{4},  0 \right\}$.
  \item 我们有$\bar{3}^2=1$. 进而易知$\left\{\bar{3}^{k}\mid k\in\NN\right\}=
    \left\{ \bar{3}, \bar{3}^2 \right\}=\left\{  \bar{3}, \bar{1} \right\}$.
  \item 我们有$\bar{5}^2=1$. 进而易知$\left\{\bar{5}^{k}\mid k\in\NN\right\}=
    \left\{ \bar{5}, \bar{5}^2  \right\}=\left\{  \bar{5}, \bar{1} \right\}$.
  \item 
    我们有$\bar{7}^2=1$. 进而易知$\left\{\bar{7}^{k}\mid k\in\NN\right\}=\left\{\bar{7}, \bar{7}^2 \right\}=\left\{  \bar{7}, \bar{1} \right\}$.
  \end{enumerate}
\end{solution}

\begin{exercise}
设 $R_{1},  R_{2}$ 是环。 记 $R=\left\{(a,  b) \mid a \in R_{1},  b \in R_{2}\right\}$,  定义
\[
(a,  b)+\left(a^{\prime},  b^{\prime}\right)=\left(a+a^{\prime},  b+b^{\prime}\right),  \quad(a,  b) \cdot\left(a^{\prime},  b^{\prime}\right)=\left(a \cdot a^{\prime},  b \cdot b^{\prime}\right)
\]
试证明 $R$ 是环 (记为 $R=R_{1} \oplus R_{2}$,  称为 $R_{1},  R_{2}$ 的 (外)直和),  求出 $R$ 的零元和么元。 当 $R_{1}=$ $R_{2}=\mathbb{Z} / 2 \mathbb{Z}$ 时， 列出 $R$ 的所有元素， 指出其零元和幺元。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
设 $R_{1},  R_{2}$ 为环， 映射 $\sigma: R_{1} \rightarrow R_{2}$ 保运算 (即 $\sigma(a+b)=\sigma(a)+\sigma(b),  \sigma(a b)=$ $\sigma(a) \sigma(b)$,  对任意 $a,  b \in R_{1}$ 成立),  则称 $\sigma$ 为环的同态映射。 如果 $\sigma$ 为环的同态映射， 且 $\sigma$ 为双射 (即一一对应),  则称 $\sigma$ 为环的同构映射， 称环 $R_{1},  R_{2}$ 同构。

\begin{enumerate}[(1)]
\item 证明 $\sigma: \mathbb{Z} \rightarrow \mathbb{Z} / m \mathbb{Z},  \sigma(a)=\bar{a}$ 是环的同态映射。

\item%(2)
试举出一个环同构的例子。
\end{enumerate}
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
\begin{enumerate}[(1)]
\item 设 $D=F[X]$ 是域 $F$ 上的多项式形式环。 试模仿整数环 $\mathbb{Z}$ 的情形， 在 $D$ 中定义同余关系 (模一个多项式 $m(X)$),  求同余类环 $R=D / m(X) D$ 中的元素 (代表)、运算， 何时 $R$ 是域? 如何求其中非零元素的逆?

\item%(2)
设 $m(X)=X^{2}+1,  D=\mathbb{R}[X]$,  求 $R=D / m(X) D=\mathbb{R}[X] /\left(X^{2}+1\right)$ (的代表元集). 试证明环 $\overline{\mathbb{R}}=\{\bar{a} \mid a \in \mathbb{R}\}$ 与 $\mathbb{R}$ 同构 (从而可将 $\bar{a}$ 与 $a$ 视为等同).
\end{enumerate}
\end{exercise}

\begin{solution}

\end{solution}

\section{同余类环 $\symbb{Z}/m\symbb{Z}$ 中的单位}


\begin{exercise}
对如下 $m$ 值， 计算 $\varphi(m)$,  并列出 $(\mathbb{Z} / m \mathbb{Z})^{*}$ 中的元素：
\[
  m=9, 10, 11, 12, 15, 16, 36, 100.
\]
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item $\varphi(9)=9\times(1-\frac{1}{3})=6$. 
      $(\mathbb{Z} / 9 \mathbb{Z})^{*}=\left\{ \bar{1},  \bar{2},  \bar{4},  \bar{5},  \bar{7},  \bar{8} \right\}$.
    \item $\varphi(10)=10\times(1-\frac{1}{2})\times (1-\frac{1}{5})=4$. 
      $(\mathbb{Z} / 10 \mathbb{Z})^{*}=\left\{ \bar{1},  \bar{3},  \bar{7},  \bar{9} \right\}$.
      \item $\varphi(11)=11\times(1-\frac{1}{11})=10$. 
        $(\mathbb{Z} / 11\mathbb{Z})^{*}=\left\{ \bar{a}\mid 1\leqslant a<11 \right\}$.
      \item $\varphi(12)=12\times(1-\frac{1}{2})\times(1-\frac{1}{3})=4$. 
      $(\mathbb{Z} / 12\mathbb{Z})^{*}=\left\{ \bar{1},  \bar{5},  \bar{7},  \overline{11} \right\}$.
    \item $\varphi(15)=15\times(1-\frac{1}{3})\times(1-\frac{1}{5})=8$. 
      $(\mathbb{Z} / 15\mathbb{Z})^{*}=\left\{ \bar{1},  \bar{2},  \bar{4},  \bar{7},  \bar{8},  \overline{11}, \overline{13},  \overline{14} \right\}$.
\item $\varphi(16)=16\times(1-\frac{1}{2})=8$. 
      $(\mathbb{Z} / 16\mathbb{Z})^{*}=\left\{ \bar{1},  \bar{3},  \bar{5},  \bar{7},  \bar{9},  \overline{11}, \overline{13},  \overline{15} \right\}$.
    \item $\varphi(36)=36\times(1-\frac{1}{2})\times(1-\frac{1}{3})=12$. 
      由于$36=2^2\times 3^2$, 要找到$\ZZ/36\ZZ$中单位，只用找到$1$到$36$之间不被$2,3$整除的整数即可。可得
      \[
        (\mathbb{Z} / 36\mathbb{Z})^{*}=\left\{ \bar{1},  \bar{5},  \bar{7},  \overline{11},  \overline{13},  \overline{17}, \overline{19},  \overline{23},  \overline{25},  \overline{29},  \overline{31},  \overline{35} \right\}.
      \]
%      我们应用Eratothenes筛法：
%       \[
%    \begin{tikzpicture}[column sep=1em, row sep=.5em]
%      \matrix (m) [matrix of math nodes, ampersand replacement=\&]
%      {
%        % 通过 ipython 把这个数表打印出来
%        \symbf{1} \& 2 \& 3 \& 4 \& \symbf{5} \& 6 \& \symbf{7} \& 8 \& 9 \& 10 \\
%        \symbf{11} \& 12 \& \symbf{13} \& 14 \& 15 \& 16 \& \symbf{17} \& 18 \& \symbf{19} \& 20 \\
%        21 \& 22 \& \symbf{23} \& 24 \& \symbf{25} \& 26 \& 27 \& 28 \& \symbf{29} \& 30 \\
%        \symbf{31} \& 32 \& 33 \& 34 \& \symbf{35} \& 36 \\
%};
%% 划去 被 2 整除的数
%\foreach \j in {1,2,3} 
%\foreach \i in {2,4,...,10} {
%  \draw (m-\j-\i.west) -- (m-\j-\i.east);
%}
%\foreach \i in {2,4,6} {
%  \draw (m-4-\i.west) -- (m-4-\i.east);
%}
%% 划去 被 3 整除的还未被划去的数
%\foreach \j/\i in {1/3,1/9, 2/5, 3/1, 3/7, 4/3} {
%\draw (m-\j-\i.south west) -- (m-\j-\i.north east);
%}
%    \end{tikzpicture}
%  \]
      
    \item $\varphi(100)=100\times(1-\frac{1}{2})\times(1-\frac{1}{5})=40$. 
      由于$100=2^2\times 5^2$, 要找到$\ZZ/100\ZZ$中单位，只用找到$1$到$100$之间不被$2,5$整除的整数即可。可得
      \[
      \begin{aligned}
        (\mathbb{Z} / 100\mathbb{Z})^{*}&= \left\{ \bar{1},  \bar{3},  \bar{7},  \bar{9},  \overline{11},  \overline{13},  \overline{17},  \overline{19},  \overline{21},  \overline{23},  \overline{27},  \overline{29},  \overline{31},  \overline{33},  \overline{37}, \right. \\
                      & \qquad \overline{39},  \overline{41},  \overline{43},  \overline{47},  \overline{49},  \overline{51},  \overline{53},  \overline{57},  \overline{59},  \overline{61},  \overline{63},  \overline{67},  \overline{69}, \\
                      & \qquad\left.\overline{71},  \overline{73},  \overline{77},  \overline{79},  \overline{81},  \overline{83},  \overline{87},  \overline{89},  \overline{91},  \overline{93},  \overline{97},  \overline{99} \right\}.
                         \end{aligned}
    \]
%我们应用Eratothenes筛法：
% \[
%    \begin{tikzpicture}[column sep=1em, row sep=.5em]
%      \matrix (m) [matrix of math nodes, ampersand replacement=\&]
%      {
%        % 通过 ipython 把这个数表打印出来
%        \symbf{1} \& 2 \& \symbf{3} \& 4 \& 5 \& 6 \& \symbf{7} \& 8 \& \symbf{9} \& 10 \\
%        \symbf{11} \& 12 \& \symbf{13} \& 14 \& 15 \& 16 \& \symbf{17} \& 18 \& \symbf{19} \& 20 \\
%        \symbf{21} \& 22 \& \symbf{23} \& 24 \& 25 \& 26 \& \symbf{27} \& 28 \& \symbf{29} \& 30 \\
%        \symbf{31} \& 32 \& \symbf{33} \& 34 \& 35 \& 36 \& \symbf{37} \& 38 \& \symbf{39} \& 40 \\
%        \symbf{41} \& 42 \& \symbf{43} \& 44 \& 45 \& 46 \& \symbf{47} \& 48 \& \symbf{49} \& 50 \\
%        \symbf{51} \& 52 \& \symbf{53} \& 54 \& 55 \& 56 \& \symbf{57} \& 58 \& \symbf{59} \& 60 \\
%        \symbf{61} \& 62 \& \symbf{63} \& 64 \& 65 \& 66 \& \symbf{67} \& 68 \& \symbf{69} \& 70 \\
%        \symbf{71} \& 72 \& \symbf{73} \& 74 \& 75 \& 76 \& \symbf{77} \& 78 \& \symbf{79} \& 80 \\
%        \symbf{81} \& 82 \& \symbf{83} \& 84 \& 85 \& 86 \& \symbf{87} \& 88 \& \symbf{89} \& 90 \\
%        \symbf{91} \& 92 \& \symbf{93} \& 94 \& 95 \& 96 \& \symbf{97} \& 98 \& \symbf{99} \& 100 \\
%};
%% 划去 被 2 整除的数
%\foreach \j in {1,2,...,10} 
%\foreach \i in {2,4,...,10} {
%  \draw (m-\j-\i.west) -- (m-\j-\i.east);
%}
%% 划去 被 5 整除的还未被划去的数
%\foreach \j in {1,...,10} {
%\draw (m-\j-5.south east) -- (m-\j-5.north west);
%}
%    \end{tikzpicture}
%  \]
    另外，也可在 SageMath 中运行如下代码获得：
\begin{minted}{sage}
sage: a = 100
sage: for i in range(1, a):
....:     if Integer(i).gcd(a) == 1:
....:         print(i)
\end{minted}
  \end{enumerate}
\end{solution}

\begin{exercise}
列出 $(\mathbb{Z} / m \mathbb{Z})^{*}$ 元素的乘法表， 各元素的逆： $m=2, 3, 4, 5, 6, 7, 8, 9, 10, 12$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
$\varphi(m)$ 是偶数还是奇数? 当 $m \geqslant n$ 时， 是否 $\varphi(m) \geqslant \varphi(n)$ ?
\end{exercise}

\begin{solution}
  除了$\varphi(1)=\varphi(2)=1$, 对$m\geqslant3$, $\varphi(m)$总是偶数。
  若$m=\prod_{i=1}^s p_i^{r_i}$的某个素因子$p_i$为奇素数，
  则$\varphi(m)=\prod_{i=1}^s p_i^{r_i-1}(p_i-1)$为偶数；
  若$m=2^r$, 其中$r\geqslant 2$, 则$\varphi(m)=2^{r-1}$亦是偶数。

  $m>n$时不见得有$\varphi(m)>\varphi(n)$. 如$\varphi(6)=2<\varphi(5)=4$.
\end{solution}

\begin{exercise}
设 $m=m_{1} m_{2}$,  且 $m_{1}$ 与 $m$ 的素因子集相同， 证明： $\varphi(m)=m_{2} \varphi\left(m_{1}\right)$.
\end{exercise}

\begin{solution}
  设$m_{1}$ 与 $m$ 的素因子集为$\left\{ p_1, \cdots, p_k \right\}$.
  那么
  \[
    \varphi(m)=m\prod_{i=1}^k(1-\frac{1}{p_i}),  \quad
    \varphi(m_1)=m_1\prod_{i=1}^k(1-\frac{1}{p_i}).
  \]
  显然$\varphi(m)=m_2\varphi(m_1)$.
\end{solution}

\begin{exercise}
解同余式 $12 x \equiv 20\left(\mod 28\right)$.
\end{exercise}

\begin{solution}
  我们有$(12, 28)=4$且$4\mid 20$. 因此$12 x \equiv 20\left(\mod 28\right)$与$3x\equiv 5\left( \mod 7 \right)$同解。
  由$5\cdot 3\equiv 1\left( \mod 7 \right)$可知$x\equiv 4\left( \mod 7 \right)$.
  因此$4$个解为$x\equiv 4, 11, 18, 25\left( \mod 28 \right)$.
\end{solution}

\begin{exercise}
设 $m \geqslant 3$,  证明： 
\begin{enumerate}[(1)]
\item 模 $m$ 既约剩余系的元素之和同余于 $0$ (模 $m$).

\item%(2)
模 $m$ 最小正既约剩余系的元素之和为 $\sigma=m \varphi(m) / 2$.
\end{enumerate}
\end{exercise}

\begin{solution}
令
\[
  S=\left\{ a\mid (a,m)=1, 1\leqslant a< \frac{m}{2} \right\},\quad
S'=\left\{ m-a\mid a\in S \right\}.
\]
那么最小正既约剩余系$\Phi_m=S\sqcup S'$, 且$\# S=\# S'$.
故
\[\tag*{\qedhere}
\sigma  = {m\varphi }\left( m\right) /2 \equiv  0\left( {\mod m}\right) .
\]
\end{solution}

\begin{exercise}
由 Euler 函数计算公式证明素数有无限多。
\end{exercise}

\begin{solution}
  反证。假设所有不同的素数只有 \({p}_{1}, \cdots, {p}_{s}\). 令$n={p}_{1}\cdots {p}_{s}$.
  按照定义$\varphi(n)$为不超过$n$且与$n$互素的正整数的个数，因此$\varphi(n)=1$.
  另一方面，由Euler公式我们有$\varphi(n)=\prod_{i=1}^s (p_i-1)$, 
  这与$\varphi(n)=1$相悖。故素数有无限多。
\end{solution}

\section{Fermat-Euler 定理}



\begin{exercise}
对 $m=5, 7, 8, 9, 10, 12, 36$,  在 $\mathbb{Z} / m \mathbb{Z}$ 中分别计算 $\bar{2}^{k},  \bar{3}^{k}$ ( $k$ 遍历正整数).
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item $m=5$. $\varphi(5)=4$. 使得$\bar{2}^{k}=1$的最小的正整数正是$k=4$.
      这样
\[
    \bar{2}^{k}=\begin{cases}
      1 & \text{若}~ k\equiv 0\left( \mod 4 \right)\\
      \bar{2} & \text{若}~ k\equiv 1\left( \mod 4 \right)\\
      \bar{2}^2=\bar{4} & \text{若}~ k\equiv 2\left( \mod 4 \right)\\
      \bar{2}^3=\bar{3} & \text{若}~ k\equiv 3\left( \mod 4 \right).
    \end{cases}
\]
类似地，
\[
   \bar{3}^{k}=\begin{cases}
      1 & \text{若}~ k\equiv 0\left( \mod 4 \right)\\
      \bar{3} & \text{若}~ k\equiv 1\left( \mod 4 \right)\\
      \bar{3}^2=\bar{4} & \text{若}~ k\equiv 2\left( \mod 4 \right)\\
      \bar{3}^3=\bar{2} & \text{若}~ k\equiv 3\left( \mod 4 \right).
    \end{cases}
\]
\item $m=8$. $\varphi(8)=4$. $\bar{2}^{3}=0$.
      这样
\[
    \bar{2}^{k}=\begin{cases}
      \bar{2} & \text{若}~ k=1\\
      \bar{2}^2=\bar{4} & \text{若}~ k=2\\
      0 & \text{若}~ k\geqslant 3.
    \end{cases}
\]
使得$\bar{3}^{k}=1$的最小的正整数正是$k=2$.
\[
   \bar{3}^{k}=\begin{cases}
      1 & \text{若}~ k\equiv 0\left( \mod 2 \right)\\
      \bar{3} & \text{若}~ k\equiv 1\left( \mod 2 \right).
    \end{cases}
\]
\item $m=36$. $36=4\times 9$. 我们有准素分解$\ZZ/36\ZZ\cong \ZZ/4\ZZ\oplus \ZZ/9\ZZ$.
  先算$\bar{2}$的正整数幂。
  注意到$2^3\equiv -1\left( \mod 9 \right)$,
  故 $2^6\equiv 1\left( \mod 9 \right)$,
  $2^6\equiv (0, 1)\left( \mod 4, 9 \right)$.
  因此对正整数$k$, $2^{6k}\equiv (0,1)^k\equiv (0,1)\left( \mod 4, 9 \right)$,
  从而$\bar{2}^{6k}=\bar{2}^6=\overline{28}$. 
  这样对正整数$k$,
  \[
      \bar{2}^{k}=\begin{cases}
      \bar{2} & \text{若}~ k=1\\
      \bar{4} & \text{若}~ k=2\\
      \bar{8} & \text{若}~ k=3\\
      \overline{16} & \text{若}~ k=4\\
      \overline{32} & \text{若}~ k=5\\
      \overline{28} & \text{若}~ k\equiv 0\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{28}\cdot \bar{2}=\overline{20} & \text{若}~ k\equiv 1\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{28}\cdot\bar{4}=\bar{4} & \text{若}~ k\equiv 2\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{28}\cdot\bar{8}=\bar{8} & \text{若}~ k\equiv 3\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{28}\cdot\overline{16}=\overline{16} & \text{若}~ k\equiv 4\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{28}\cdot\overline{32} =\overline{32}& \text{若}~ k\equiv 5\left( \mod 6 \right)\text{~且~} k\geqslant 6.
    \end{cases}
  \]
  总结下就是：
  \[
      \bar{2}^{k}=\begin{cases}
      \bar{2} & \text{若}~ k=1\\
      \bar{4} & \text{若}~ k\equiv 2\left( \mod 6 \right)\text{~且~} k\geqslant 1\\
      \bar{8} & \text{若}~ k\equiv 3\left( \mod 6 \right)\text{~且~} k\geqslant 1\\
      \overline{16} & \text{若}~ k\equiv 4\left( \mod 6 \right)\text{~且~} k\geqslant 1\\
      \overline{32} & \text{若}~ k\equiv 5\left( \mod 6 \right)\text{~且~} k\geqslant 1\\
      \overline{28} & \text{若}~ k\equiv 0\left( \mod 6 \right)\text{~且~} k\geqslant 6\\
      \overline{20} & \text{若}~ k\equiv 1\left( \mod 6 \right)\text{~且~} k\geqslant 6.
    \end{cases}
  \]
  再算$\bar{3}$的正整数幂。$3^2\equiv 1\left( \mod 4 \right)$. 
  于是$3^2\equiv (1,0)\left( \mod 4,9 \right)$, 进而
  对正整数$k$, $3^{2k}\equiv (1,0) \left( \mod 4,9 \right)$,
  即$3^{2k}\equiv 3^2=9\left( \mod 36 \right)$.
  这样
  \[
      \bar{3}^{k}=\begin{cases}
      \bar{3} & \text{若}~ k=1\\
      \bar{9} &  \text{若}~ k\equiv 0\left( \mod 2 \right)\text{~且~} k\geqslant 2 \\
      \bar{9}\cdot \bar{3}=\overline{27} &  \text{若}~ k\equiv 1\left( \mod 2 \right)\text{~且~} k\geqslant 2.
    \end{cases}
  \]
  \end{enumerate}
\end{solution}

\begin{exercise}
在上题中， 是否存在正整数 $g$,  使 $\bar{g}^{k}$ 遍历 $(\mathbb{Z} / m \mathbb{Z})^{*}$ ?
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
对 $m=8, 16$,  在 $\mathbb{Z} / m \mathbb{Z}$ 中计算 $\bar{3}^{k},  \bar{5}^{k}$ ($k$ 遍历正整数).
\end{exercise}

\begin{solution}
  我们只对$m=16$计算。$\varphi(16)=8$. 故$3^8\equiv 1\equiv 5^8\left( \mod 16 \right)$.
  实际上，使得$\bar{3}^{k}=1$的最小的正整数$k$是$k=4$, 使得$\bar{5}^{k}=1$的最小的正整数$k$亦是$k=4$.
  因此，
  \[
    \begin{gathered}
    \bar{3}^{k}=\begin{cases}
      1 & \text{若}~ k\equiv 0\left( \mod 4 \right)\\
      \bar{3} & \text{若}~ k\equiv 1\left( \mod 4 \right)\\
      \bar{3}^2=\bar{9} & \text{若}~ k\equiv 2\left( \mod 4 \right)\\
      \bar{3}^3=\overline{11} & \text{若}~ k\equiv 3\left( \mod 4 \right),
    \end{cases}
    \\
    \bar{5}^{k}=\begin{cases}
      1 & \text{若}~ k\equiv 0\left( \mod 4 \right)\\
      \bar{5} & \text{若}~ k\equiv 1\left( \mod 4 \right)\\
      \bar{5}^2=\bar{9} & \text{若}~ k\equiv 2\left( \mod 4 \right)\\
      \bar{5}^3=\overline{13} & \text{若}~ k\equiv 3\left( \mod 4 \right).
    \end{cases}
    \end{gathered}
  \]
\end{solution}

\begin{exercise}
设 $(a,  m)=1$,  使 $a^{k} \equiv 1\left(\mod m\right)$ 成立的最小正整数 $k_{0}$ 称为 $a$ 的模 $m$ 阶。 求证：
\[
a^{k} \equiv 1 \quad\left(\mod m\right)
\]
当且仅当 $k_{0} \mid k$.
\end{exercise}

\begin{solution}
  ($\Leftarrow$) 显然。

  ($\Rightarrow$) 令\(k = {k}_{0}q + r\), 其中$0\leqslant r<k_0$.  那么
  \[1\equiv {a}^{k} = {a}^{{k}_{0}q + r} \equiv {a}^{r} \left( \mod m \right).\]
    由$k_0$的最小性知$r=0$, 故$k_0\mid k$.
\end{solution}

\begin{exercise}
求 $2^{2015}$ 除以 $19$ 的余数。
\end{exercise}

\begin{solution}
  由Euler定理知$1=2^{\varphi(19)}=2^{18}$.
  注意到$2015=18\times 112 -1$. 故$2^{2015}\equiv 2^{-1}\left( \mod 19 \right)$.
  由于$2\times (-9) + 19=1$, 我们知$2\left( \mod 19 \right)$的逆为$-9\equiv 10\left( \mod 19 \right)$.
  因此$2^{2015}$ 除以 $19$ 的余数为$10$.
\end{solution}

\begin{exercise}
证明： $30 \mid\left(n^{25}-n\right)$ (对任意整数 $n$).
\end{exercise}

\begin{solution}
  由于$30=2\cdot 3\cdot 5$, 只用证明$2, 3, 5$都整除$n^{25}-n$. 
  令$p=2,3$或$5$.
  若$p\mid n$, 显然有$p\mid n^{25}-n$. 
  设$p\nmid n$.
  由Fermat小定理知
  \(
    n^{p-1}\equiv 1\left( \mod p \right).
  \)
  由于$25\equiv 1\left( \mod (p-1) \right)$, 
  我们有
  \(
    n^{25}\equiv n\left( \mod p \right),
  \)
  即$p\mid n^{25}-n$. 故总有$p\mid n^{25}-n$.
  证毕。
\end{solution}

\begin{remark}
  一般地，若$m>1$为无平方因子的正整数，$n\equiv 1\left( \mod \varphi(m) \right)$, 则对任意整数$a$有
  \(
    a^n\equiv a\left( \mod m \right).
  \)
  诚然，令$m=p_1 p_2 \cdots p_t$为素因子分解，其中$p_i$互异。
  只用证明$a^n\equiv a\left( \mod p \right)$, 对任意的$p=p_1,\cdots,p_{t-1}$或 $p_t$.
  若$p\mid a$, 显然有$a^n\equiv a\left( \mod p \right)$. 否则，
  由Fermat小定理知$a^{p-1}\equiv 1\left( \mod p \right)$.
  我们有$\varphi(m)=\prod_{i=1}^t(p_i-1)$. 
  由于$p-1\mid \varphi(m) \mid n-1$,
亦有
\(
  a^n\equiv a\left( \mod p \right).
\)
因此总有$a^n\equiv a\left( \mod p \right).$证毕。

对任意的正整数$m$, 若$(a,m)=1$, 则$\ord_m a\mid \varphi(m)$, 故亦有
$a^n\equiv a\left( \mod m \right).$
若$m$有平方因子且$a,m$不互素，不见得有$a^n\equiv a\left( \mod m \right).$
例如，令$m=p^{2}, a=p, n=\varphi(m)+1=p(p-1)+1$. 显然
$a^n \equiv 0\nequiv a \left( \mod m \right)$.
\end{remark}

\begin{exercise}
设 $n \geqslant 3$,  证明： $a^{2^{n-2}} \equiv 1\left(\mod 2^{n}\right)$ 对任意奇数 $a$ 成立。
\end{exercise}

\begin{solution}
  我们对$n\geqslant 3$归纳来证明$2^n\mid (a^{2^{n-2}}-1)$. 
  设$n=3$. 令$a=2k+1$. 那么
  \[
    a^2=(2k+1)^2=4k(k+1)+1\equiv 1\left( \mod 8 \right).
  \]
  故确有$2^3\mid (a^2-1)$.
  再设$n>3$.
  由归纳假设知
  $2^{n-1}\mid a^{2^{n-3}}-1$. 又$a^{2^{n-3}}+1$是偶数，我们有
  \[
    2^n\mid ( a^{2^{n-3}}-1) ( a^{2^{n-3}}+1) =2^{2^{n-2}}-1.
  \]
  归纳完毕。因此$n\geqslant3$时总有 $2^n\mid a^{2^{n-2}} -1$.
\end{solution}

\begin{exercise}
  设 $n \geqslant 2$,  证明： 使 $5^{k} \equiv 1\left(\mod 2^{n}\right)$ 成立的最小正整数为 $k=k_{0}=2^{n-2}$.
\end{exercise}

\begin{solution}
  容易验证$n=2,  3$时断言成立。可设$n>3$. 
  由练习7知$5^{2^{n-2}} \equiv 1\left( \mod 2^n \right)$. 
  这样根据练习4,  要证明$k_0=2^{n-2}$,  只用证明
  \[
    5^{2^{n-3}} \nequiv 1\left( \mod 2^n \right).
  \]
  我们反证，假设存在$n> 3$使得
  $5^{2^{n-3}} \equiv 1\left( \mod 2^n \right)$.
  这样可取最小的使得此式成立的$n$. 我们有$n\geqslant 4$.
  由练习7知$5^{2^{n-4}}\equiv 1\left( \mod 2^{n-2} \right)$,  
  故
  $5^{2^{n-4}}\equiv 1\left( \mod 4 \right)$, 
  这样
  $5^{2^{n-4}}\nequiv -1\left( \mod 4 \right), $
  即
  \[
    4\nmid 5^{2^{n-4}}+1.
  \]
  既然
  \[
    2^n \mid 5^{2^{n-3}} - 1= (5^{2^{n-4}}-1)(5^{2^{n-4}}+1).
  \]
  且$5^{2^{n-4}}+1$为不被$4$整除的偶数，我们有
  \[
    2^{n-1}\mid 5^{2^{n-4}}-1.
  \]
  这与$n$的最小性矛盾了。这就证明了
  不存在$n\geqslant 4$使得
  $5^{2^{n-3}} \equiv 1\left( \mod 2^n \right)$.
  故$n\geqslant 4$时总有
  $5^{2^{n-3}} \nequiv 1\left( \mod 2^n \right)$.
  证毕。

  上面的证明虽然正确但是不好。实际上，容易归纳地证明一个更精细的结果：
  \[
    5^{2^{n-3}}\equiv 1+2^{n-1}\left( \mod 2^{n} \right).
  \]
  由此容易得到$\operatorname{ord}_{2^n}(5)=2^{n-2}$.
  参见\S3.3中定理1.
\end{solution}

\begin{exercise}
设 $m=2^{n}$,  其中 $n \geqslant 3$. 证明：模 $m$ 的既约剩余系可以取为
\[
  \left\{(-1)^{\delta} 5^{k}\right\} \quad\left(\delta=0, 1 ; k=0, 1,  \cdots,  2^{n-2}-1\right).
\]
\end{exercise}

\begin{solution}
  显然$(-1)^{\delta} 5^{k}$与$2^n$互素。
  由练习8知$2^{n-2}$为最小的正整数$k$使得$5^k\equiv 1\left( \mod m \right)$.
  这样
  \[
    5^{k}\quad (k=0, 1, \cdots, 2^{n-2}-1)
  \]
  这$2^{n-2}$个数中任何两个都模$m$不同余。
  从而
  \[
    -5^{k}\quad  (k=0, 1, \cdots, 2^{n-2}-1)
  \]
  这$2^{n-2}$个数亦是如此。
  另外，我们还有：对任意的整数$k,  l$, 
  \[
    5^k\nequiv -5^l\left( \mod 2^{n-2} \right), 
  \]
  因为
  \[
    5^k\equiv 1\nequiv -1\equiv -5^l\left( \mod 4 \right).
  \]
  这样
  \[
    (-1)^{\delta} 5^{k} \quad\left(\delta=0, 1 ; k=0, 1,  \cdots,  2^{n-2}-1\right)
  \]
  这$2^{n-1}$个数中任何两个都模$m$不同余，
  而模$m$的既约剩余系中元素个数恰好为
  \[
    \varphi(m)=\varphi(2^n)=2^n(1-\frac{1}{2})=2^{n-1}, 
  \]
  故上面的$2^{n-1}$个与$m$互素的数就构成了一个模$m$的既约剩余系。
\end{solution}

\begin{exercise}
[Wilson 定理推广]
  设 $p$ 为奇素数， 证明：
\[
  \left[\left(\frac{p-1}{2}\right)!\right]^{2}(-1)^{(p-1) / 2} \equiv-1 \quad\left(\mod p\right).
\]
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
容斥原理是： 若 $S_{1},  \cdots,  S_{m}$ 为有限集合， 证明：
\[
\left|S_{1} \cup \cdots \cup S_{m}\right|=\sum_{i}\left|S_{i}\right|-\sum_{i<j}\left|S_{i} \cap S_{j}\right|+\sum_{i<j<k}\left|S_{i} \cap S_{j} \cap S_{k}\right|-\cdots
\]
试用容斥原理证明 $\boldsymbol{\varphi}(n)=n \prod_{p \mid n}(1-1 / p)$. (提示： 考虑每个 $p \mid n$ 在模 $n$ 环中的重数。)
\end{exercise}

\begin{solution}

\end{solution}

\section{孙 子 定理}


\begin{exercise}
[秦王暗点兵]
  秦兵列队， 每列百人则余一人， 九十九人则余二人， 百零一人则不足二人。 问秦兵几何?
\end{exercise}

\begin{solution}
所给问题相当于解同余方程组
\[
  \begin{cases} 
    x \equiv 1\left(\mod 100 \right) \\ 
    x \equiv 2\left(\mod 99\right) \\ 
    x \equiv -2\left(\mod 101\right).
  \end{cases}
\]
  我们应用孙子定理的解法二中的算法，和记号。
    此时
    \[
      m_1=100, m_2=99, m_3=101,  b_1=1, b_2=2, b_3=-2.
    \]
    故
    \[
      M_1=m_2m_3=99\times 101, \quad M_2=m_1m_3=100 \times101, \quad M_3=m_1m_2=100\times 99.
    \]
    接着来找$u_1, u_2, u_3$使得
    \[
      u_1M_1\equiv 1\left( \mod m_1 \right), \quad
      u_2M_2\equiv 1\left( \mod m_2 \right), \quad
      u_3M_3\equiv 1\left( \mod m_3 \right), 
    \]
      或者说，
      \[
        -u_1\equiv 1\left( \mod 100\right), \quad
        2u_2\equiv 1\left( \mod 99\right), \quad 
        2u_3\equiv 1\left( \mod 101\right).
      \]
      可取
        \[
          u_1=-1,  \quad u_2=50,  \quad u_3=51.
        \]
于是
\[
  e_1=u_1M_1=-9999, \quad e_2=u_2M_2=505000, \quad e_3=u_3M_3=504900.
\]
那么解为
   \[
     x \equiv b_1e_1+b_2e_2+b_3e_3= -9799\equiv 990101\left(\mod 999900\right).
   \]
   最小整数解为$990101$.
\end{solution}

\begin{exercise}
颐和园向北的水渠上， 设每十一里有一凉亭， 每七里一大桥， 五里一小桥。 一游人出一凉亭， 北行一里见一大桥， 再北行一里， 见前面一里有小桥。 问游人现在何处?
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
某数被 $3$ 除余 $2$,  被 $4$ 除余 $1$,  被 $5$ 除余 $3$,  求此数。
\end{exercise}

\begin{solution}
所给问题相当于解同余方程组
\[
  \begin{cases} 
    x \equiv 2\left(\mod 3 \right) \\ 
    x \equiv 1\left(\mod 4\right) \\ 
    x \equiv 3\left(\mod 5\right).
  \end{cases}
\]
  我们应用孙子定理的解法二中的算法，和记号。
    此时
    \[
      m_1=3, m_2=4, m_3=5,  b_1=2, b_2=1, b_3=3.
    \]
    故
    \[
      M_1=m_2m_3=4\times 5, \quad M_2=m_1m_3=3\times 5, \quad M_3=m_1m_2=3\times 4.
    \]
    接着来找$u_1, u_2, u_3$使得
    \[
      u_1M_1\equiv 1\left( \mod m_1 \right), \quad
      u_2M_2\equiv 1\left( \mod m_2 \right), \quad
      u_3M_3\equiv 1\left( \mod m_3 \right), 
    \]
      或者说，
      \[
        2u_1\equiv 1\left( \mod 3\right), \quad
        -u_2\equiv 1\left( \mod 4\right), \quad 
        2u_3\equiv 1\left( \mod 5\right).
      \]
      可取
        \[
          u_1=2,  \quad u_2=-1,  \quad u_3=3.
        \]
于是
\[
  e_1=u_1M_1=40, \quad e_2=u_2M_2=-15, \quad e_3=u_3M_3=36.
\]
那么解为
   \[
     x \equiv b_1e_1+b_2e_2+b_3e_3\equiv 53\left(\mod 60\right).
   \]
\end{solution}

\begin{exercise}
求 $f(x)$ 使其被 $(x-1)^{2}$ 除余 $x$,  被 $(x+1)^{2}$ 除余 $x-1$.
\end{exercise}

\begin{solution}
  令$m_1=(x-1)^{2}, m_2=(x+1)^{2}$, $M_1=m_2, M_2=m_1$.
  我们有$(M_1, M_2)=1$, 且辗转相除可得相应的B\'ezout等式为
  \[
    \left(-\frac{1}{4}x+\frac{1}{2}\right)(x+1)^2+\left(\frac{1}{4}x+\frac{1}{2}\right) (x-1)^2=1.
  \]
  令
  \[
    e_1= \left(-\frac{1}{4}x+\frac{1}{2}\right)(x+1)^2,\quad 
    e_2=\left(\frac{1}{4}x+\frac{1}{2}\right) (x-1)^2.
  \]
  因此
  \[\tag*{\qedhere}
    f\equiv x\cdot e_1+(x-1)\cdot e_2=-\frac{1}{4}x^3 + \frac{7}{4}x - \frac{1}{2}\left( \mod (x-1)^2(x+1)^2 \right).
  \]
\end{solution}

\begin{exercise}
将前面几题写为同余类环的直和分解形式， 并判断所求元素是否可逆， 并求其逆。
\end{exercise}

\begin{solution}
我们以第3题为例。我们有环的内直和分解和外直和分解：
\[
  \ZZ/60\ZZ=\ZZ \overline{40}\oplus_{\text{in}} \ZZ \overline{-15}\oplus_{\text{in}} \ZZ \overline{36}\cong 
  \ZZ/3\ZZ\oplus_{\text{ex}} \ZZ/4\ZZ\oplus_{\text{ex}} \ZZ/5\ZZ.
\]
$53$在$R=\ZZ/3\ZZ\oplus_{\text{ex}} \ZZ/4\ZZ\oplus_{\text{ex}} \ZZ/5\ZZ$中的像为
$(\overline{53}, \overline{53}, \overline{53})=(\overline{-1}, \bar{1}, \bar{3})$.
此元素为$R$中可逆元，逆为$(\overline{-1}, \bar{1}, \bar{2})$.
此逆对应于$\ZZ/60\ZZ$中$-\bar{e}_1+\bar{e}_2+2\bar{e}_3=\overline{17}$.
故在$\ZZ/60\ZZ$中$\overline{53}^{-1}=\overline{17}$.
另外，辗转相除可知$53, 60$的B\'ezout等式为$17\times 53-15\times 60=1$, 由此亦可知
$53\left( \mod 60 \right)$的逆为$17$.
\end{solution}

\begin{exercise}
[孙子定理推广]
  设 $m_{1},  \cdots,  m_{s}$ 和 $b_{1},  \cdots,  b_s$ 均为任意整数。 则一次同余式组
\[
x \equiv b_{i} \quad\left(\mod m_{i}\right) \quad(1 \leqslant i \leqslant s)
\]
有整数解当且仅当
\[
\left(m_{i},  m_{j}\right) \mid\left(b_{i}-b_{j}\right) (\text {对任意~} 1 \leqslant i < j \leqslant s). 
\]
且此时， 解集是模 $m=\left[m_{1},  \cdots,  m_{s}\right]$ (最小公倍) 的一个同余类 $x_{0}+m k$ ($k\in\ZZ$).
\end{exercise}

\begin{solution}
  ($\Rightarrow$)是显然的，我们证明($\Leftarrow$). 我们对$s$归纳。$s=1$时断言平凡。
  考虑$s=2$. 令$d=(m_1,m_2)$. 由于$d\mid (b_1-b_2)$, 可设$b_1=dq_1+r, b_2=dq_2+r$.
  由于$(\frac{m_1}{d}, \frac{m_2}{d})=1$, 孙子定理告诉我们
  \[
    \begin{cases}
      y\equiv q_1\left( \mod \frac{m_1}{d} \right)\\
      y\equiv q_2\left( \mod  \frac{m_2}{d}\right)
    \end{cases}
  \]
  有解。令$y_0$为一个解，即
   \[
    \begin{cases}
      y_0\equiv q_1\left( \mod \frac{m_1}{d} \right)\\
      y_0\equiv q_2\left( \mod  \frac{m_2}{d}\right).
    \end{cases}
  \]
 那么
   \[
    \begin{cases}
      dy_0+r\equiv dq_1+r=b_1\left( \mod m_1 \right)\\
      dy_0+r\equiv dq_2+r=b_2\left( \mod  m_2\right).
    \end{cases}
  \]
  因此$dy_0+r$为
  \[
    \begin{cases}
      x\equiv b_1\left( \mod m_1 \right)\\
x\equiv b_2\left( \mod m_2 \right)
    \end{cases}
  \]
  的一个解。
  最后考虑$s>2$. 由归纳假设知
  \[
x \equiv b_{i} \quad\left(\mod m_{i}\right) \quad(1 \leqslant i \leqslant s-1)
\]
有解$x_0$. 这样
 \[
x \equiv b_{i} \quad\left(\mod m_{i}\right) \quad(1 \leqslant i \leqslant s)
\]
等价于
 \[
   \begin{cases}
     x\equiv x_0\left( \mod m_1 \right)\\
     \quad \vdots \\
     x\equiv x_0\left( \mod m_{s-1} \right)\\
     x\equiv b_s \left( \mod m_s \right),
   \end{cases}
\]
亦等价于
\[
   \begin{cases}
     x\equiv x_0\left( \mod [m_1,\cdots,m_{s-1}] \right)\\
    x\equiv b_s \left( \mod m_s \right).
   \end{cases}
\]
对$1\leqslant i<s$, 由于$m_i\mid x_0-b_i$且$(m_i, m_s)\mid (b_i-b_s)$, 
我们有$(m_s, m_i)\mid x_0-b_s$. 注意到%
\footnote{可如下证明。
  令$p$为任意的素数. 由于($*$)两边关于$m_1,\cdots,m_{s-1}$轮换对称，可设
  $v_p(m_1)\geqslant \cdots \geqslant v_p(m_{s-1})$. 这样
  \[
  \begin{aligned}
      v_p\left( (m_s, [m_1,\cdots,m_{s-1}])\right)&= 
      \min\left\{v_p(m_s), v_p([m_1,\cdots,m_{s-1}])\right\}\\
      &=\min\left\{v_p(m_s), v_p(m_1)\right\} \\
      &= \max\left\{ \min\left\{ v_p(m_s), v_p(m_i)\mid 1\leqslant i<s \right\} \right\}\\
      &= v_p\left( \left(  [(m_s, m_1),\cdots,(m_s,m_{s-1})]\right) \right).
    \end{aligned}
\]
因此 $(m_s, [m_1,\cdots,m_{s-1}]) = [(m_s, m_1),\cdots,(m_s,m_{s-1})].$
}
\[\tag{$*$}
  (m_s, [m_1,\cdots,m_{s-1}]) = [(m_s, m_1),\cdots,(m_s,m_{s-1})],
\]
我们有
\[
 (m_s, [m_1,\cdots,m_{s-1}]) \mid x_0-b_s.
\]
这就把解的存在性归结到$s=2$的情形，而$s=2$的情形已证，故解存在。

  若$x_0$为一解，则$x$为解当且仅当$x\equiv x_0\left( \mod m_i \right)$, 对任意的$i$.
  后者反过来相当于$x\equiv x_0\left( \mod m \right)$,
  即解集为 $x_{0}+m k$ ($k\in\ZZ$).
\end{solution}

\begin{exercise}
求解非线性同余式组：
\[
\begin{cases}x^{2} \equiv 1 & \left(\mod 3\right) \\ x \equiv 2 & \left(\mod 4\right)\end{cases}
\]
(由此可知，有时孙子定理也可用来解非线性同余式组).
\end{exercise}

\begin{solution}
$x^{2} \equiv 1 \left(\mod 3\right)$等价于$x\equiv 1 \left(\mod 3\right)$或
$x\equiv -1 \left(\mod 3\right)$.
这样所给同余方程组等价于
\[
\begin{cases}x \equiv 1 & \left(\mod 3\right) \\ x \equiv 2 & \left(\mod 4\right)\end{cases}
\quad\text{或}\quad
\begin{cases}x \equiv -1 & \left(\mod 3\right) \\ x \equiv 2 & \left(\mod 4\right)\end{cases}.
\]
令$m_1=3, m_2=4, M_1=4, M_2=3$.
$M_1, M_2$的B\'ezout等式为$4-3=1$. 
故$e_1=4, e_2=-3$.
这样
\[
  \begin{cases}x \equiv 1 & \left(\mod 3\right) \\ x \equiv 2 & \left(\mod 4\right)\end{cases}
\]
的解为
$x\equiv 4-3\times 2=-2\left( \mod 12 \right)$;
\[
  \begin{cases}x \equiv -1 & \left(\mod 3\right) \\ x \equiv 2 & \left(\mod 4\right)\end{cases}
\]
的解为
$x\equiv -4-3\times 2\equiv 2\left( \mod 12 \right)$.
总之可得所给同余方程组的解为$x\equiv \pm 2\left( \mod 12 \right)$.
\end{solution}

